package wh.排序算法.折半排序;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/1/5 11:32
 * @description:
 * @version:
 */
//折半插入排序
import java.util.Arrays;

public class BinaryInsertion_sort {
    public static void main(String[] args) {
        int[] arr = {2,3,4,4,4};//此处为自己编写的产生指定随机数组的方法，可替换为自己的数组使用。
        System.out.println(Arrays.toString(arr));
        System.out.println();

        for (int i = 1; i < arr.length; i++) {
            Insert(arr, 0, i - 1, i);
            //System.out.println(Arrays.toString(arr));
        }
        System.out.println(Arrays.toString(arr));
    }

    public static void Insert(int[] arr, int low, int high, int target) {
        if (low <= high) {//终止条件
            int mid = (low + high) / 2;//中间值

            if (arr[target] < arr[mid]) {//判断插入区间
                high = mid - 1;
            } else {
                low = mid + 1;
            }
            Insert(arr, low, high, target);//递归
        }else {//依次将其他元素后移
            int temp = arr[target];
            for (int i = target; i > low; i--) {
                arr[i] = arr[i - 1];
            }
            arr[low] = temp;//插入目标元素
        }
    }
}
